#include <stdio.h>
#include <stdlib.h>
//#include <unistd.h>//在window操作系统下要屏蔽此条指令
#include <string.h>
#ifndef _UNISTD_H
#define _UNISTD_H
#include <IO.H>
#include <PROCESS.H>
#endif
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define total_instruction 320 //指令流长
#define total_vp 32 //虚页长
#define clear_period 50 //清周期

//页面结构
typedef struct
{
    int pn, pfn, counter, time;  //定义页面序号 页面所在内存区的帧号 单位时间内访问次数 上次访问的时间
}pl_type;
pl_type pl[total_vp];  //页面结构数组

struct pfc_struct  //页面控制结构
{
    int pn, pfn; //定义页面号 内存区页面的帧号
    struct pfc_struct *next;  //页面指针，用于维护内存缓冲区的链式结构
};

typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],  //主存区页面控制结构数组
            *freepf_head,  //主存区页面控制结构的空闲页面头指针
            *busypf_head,  //主存区页面控制结构的忙页面头指针
            *busypf_tail;  //主存区页面控制结构的忙页面尾指针

int diseffect;  //页错误计数器（首次将页面载入主存时也当作页错误）
int a[total_instruction]; //随即指令流数组
int page[total_instruction];  //指令对应的页面号
int offset[total_instruction];  //指令所在的页面中的偏移量

int initialize(int);  //初始化页面结构数组和页面控制结构数组
int FIFO(int);  //先进先出算法
int LRU(int);  //最近最久未使用算法
int OPT(int);  //最佳置换算法
int CLOCK(int);  //时钟算法

int main()
{
    int s;  //随机数
    int i;
    srand(10 * getpid() % 266);  //根据每次运行时的进程号不同，获取不同的随机数种子
    s = (int)((float)(total_instruction-1) * (rand()/(RAND_MAX + 1.0)));
    //产生指令队列
    for (i=0; i<total_instruction; i+=4)
    {
        a[i] += s;  //任选一指令访问点m
        a[i+1] = a[i] + 1;  //顺序执行一条指令
        a[i+2] = (int)((float)a[i] * (rand()/(RAND_MAX + 1.0)));  //执行前地址指令m'
        a[i+3] = a[i+2] + 1;
        printf("%6d%6d%6d%6d\n", a[i], a[i+1], a[i+2], a[i+3]);
        s = (int)((float)((total_instruction-1)-a[i+2]) * (rand()/(RAND_MAX + 1.0))) + a[i+2];
    }
    printf("-----------------------------------------------------------\n");
    //将指令序列变换为页地址流
    for (i=0; i<total_instruction; i++)
    {
        page[i] = a[i]/10;
        offset[i] = a[i]%10;
    }
    printf("\n-------------不同页面工作区各种替换策略的命中率表------------\n");
    printf("Page\t  FIFO\t  LRU\t  OPT\t  CLOCK\t\n");
    //用户内存工作区从个页面到个页面
    for (i=4; i<=32; i++)
    {
        printf("%2d\t", i);
        FIFO(i);
        LRU(i);
        OPT(i);
        CLOCK(i);
        printf("\n");
    }
    system("Pause");
}

//初始化页面结构数组和页面控制结构数组
//total_pf: 用户进程的内存页面数
int initialize(int total_pf)
{
    int i;
    diseffect = 0;
    for (i=0; i<total_vp; i++)
    {
        pl[i].pn = i;
        pl[i].pfn = INVALID;  //置页面所在主存区的帧号为-1，表示该页不在主存中
        pl[i].counter = 0;  //置页面结构中的访问次数为0
        pl[i].time = -1;  //置页面结构中的上次访问的时间为-1
    }
    for (i=0; i<total_pf-1; i++)
    {
        pfc[i].next = &pfc[i+1];  //建立pfc[i-1]和pfc[i]之间的链接
        pfc[i].pfn = i;  //初始化主存区页面的帧号
    }
    pfc[total_pf-1].next = NULL;
    pfc[total_pf-1].pfn = total_pf-1;
    freepf_head = &pfc[0];  //主存区页面控制结构的空闲页面头指针指向pfc[0]
    return 0;
}

//最近最久未使用算法
//int total_pf: 用户进程的内存页面数
int LRU(int total_pf)
{
    int MinT;  //最小的访问时间，即很久没被访问过
    int MinPn;  //拥有最小的访问时间的页号
    int i, j;
    int CurrentTime;  //系统当前时间
    initialize(total_pf);  //初始化页面结构数组和页面控制数组
    CurrentTime = 0;
    diseffect = 0;
    for (i=0; i<total_instruction; i++)
    {
        if (pl[page[i]].pfn == INVALID)  //页面失效
        {
            diseffect++;  //页错误次数增加
            if (freepf_head == NULL)  //无空闲页面
            {
                MinT = 100000;
                //找出time的最小值，表明该页很久没被访问
                for (j=0; j<total_vp; j++)
                {
                    if (MinT > pl[j].time && pl[j].pfn != INVALID)
                    {
                        MinT = pl[j].time;
                        MinPn = j;
                    }
                }
                freepf_head = &pfc[pl[MinPn].pfn];  //最近没被访问过的页被释放
                pl[MinPn].pfn = INVALID;  //最近没被访问过的页被换出主存
                pl[MinPn].time = -1;  //最久没被访问过的页的访问时间置为无效
                freepf_head -> next = NULL;
            }
            pl[page[i]].pfn = freepf_head -> pfn;  //有空闲页面，把相应的页面换入主存，并把pfn改为相应的帧号
            pl[page[i]].time = CurrentTime;  //令访问时间为当前系统时间
            freepf_head = freepf_head -> next;  //减少一个空闲页面
        }
        else
            pl[page[i]].time = CurrentTime;  //命中则刷新该单元的访问时间
        CurrentTime++;  //系统当前时间加
    }
    printf("%6.3f\t", 1-(float)diseffect/320);
    return 0;
}

//最佳置换算法
//int total_pf: 用户进程的内存页面数
int OPT(int total_pf)
{
    int i, j;
    int MaxD;  //将来最近一次访问的距离的最大值（以时间单元度量）
    int MaxPn;  //将来最近一次访问的距离的最大值的页号
    int dis;  //距离计数器
    int dist[total_vp];  //距离数组，保存距离上一次访问的时间差距个数
    initialize(total_pf);  //初始化页面结构数组和页面控制结构数组
    diseffect = 0;
    for (i=0; i<total_instruction; i++)
    {
        if (pl[page[i]].pfn == INVALID)  //页面无效
        {
            diseffect++;  //页错误次数加
            //无空闲页面
            if (freepf_head == NULL)
            {
                for (j=0; j<total_vp; j++)
                {
                    if  (pl[j].pfn != INVALID)  //如果该页在主存中
                        dist[j] = 100000;  //该页关联的距离值改为最大值
                    else
                        dist[j] = 0;  //如果不在该页主存中，该页关联的距离值改变
                }
                dis = 1;  //初始距离值为1
                //从要替换的指令的下一条算起
                for (j=i+1; j<total_instruction; j++)
                {
                    //如果该页在主存中，并且是将要最近访问的页
                    if (pl[page[j]].pfn != INVALID && pl[page[i]].counter == 0)
                    {
                        dist[page[j]] = dis;  //距离值改为dis
                        pl[page[j]].counter = 1;  //使访问次数标志加，区别第一次访问和第二次访问
                    }
                    dis++;
                }
                MaxD = -1;
                for (j=0; j<total_vp; j++)
                {
                    pl[j].counter = 0;  //重置访问次数
                    //查找将来最近一次访问最大距离值及其序号
                    if (MaxD < dist[j])
                    {
                        MaxD = dist[j];
                        MaxPn = j;
                    }
                }
                freepf_head = &pfc[pl[MaxPn].pfn];  //替换将来一段时间最久访问的页
                freepf_head -> next = NULL;
                pl[MaxPn].pfn = INVALID;
            }
            pl[page[i]].pfn = freepf_head -> pfn;  //将当前页换入主存中，并且把当前页的pfn改为换入页的帧号
            freepf_head = freepf_head -> next;  //减少一个空闲页面
        }
    }
    printf("%6.3f\t", 1-(float)diseffect/320);
}

//简单时钟算法
//int total_pf: 用户进程的内存页面数
int CLOCK(int total_pf)
{
    int i;
    int use[total_vp];  //使用位
    int swap;
    swap = 0;  //发生替换
    initialize(total_pf);
    pfc_type *pnext;  //时钟指针
    pfc_type *head;  //队列头指针
    pnext = freepf_head;
    head = freepf_head;
    //初始化使用位为0
    for (i=0; i<total_vp; i++)
    {
        use[i] = 0;
    }
    diseffect = 0;
    for (i=0; i<total_instruction; i++)
    {
        //页面失效，不在主存中
        if (pl[page[i]].pfn == INVALID)
        {
            diseffect++;  //页错误次数增加
            //无空闲页面
            if (freepf_head == NULL)
            {
                //若时钟指针指向的页的使用位为1，则改为0并跳过
                while (use[pnext -> pfn] == 1)
                {
                    use[pnext -> pfn] = 0;
                    pnext = pnext -> next;
                    if (pnext == NULL)
                        pnext = head;  //如果时钟指针到达队列尾部，重新返回头部
                }
                //换出被替换的页
                pl[pnext -> pn].pfn = INVALID;
                swap = 1;
            }
            //如果使用位为0，则换入相应的页
            if (use[pnext -> pfn] == 0)
            {
                pl[page[i]].pfn = pnext -> pfn;  //页面结构中要标记帧号
                pnext -> pn = page[i];  //页面控制结构中要标记页号
                use[pnext -> pfn] = 1;  //重置使用位为1
                pnext = pnext -> next;  //时钟指针下移
                if (pnext == NULL)
                    pnext = head;  //如果时钟指针到达队列尾部，重新返回头部
                if (swap == 0)
                    freepf_head = freepf_head -> next;
            }
        }
        else
        {
            //如果页面在主存中
            use[pl[page[i]].pfn] = 1;  //刷新使用位为1
        }
    }
    printf ("%6.3f\t", 1-(float)diseffect/320);
    return 0;
}

//先进先出算法
//int total_pf: 用户进程的内存页面数
//实现细节由CLOCK算法退化而来，与FIFO同效果
int FIFO(int total_pf)
{
    int i;
    int use[total_vp];
    int swap = 0;
    initialize(total_pf);
    pfc_type *pnext, *head;
    pnext = freepf_head;
    head = freepf_head;
    for (i=0; i<total_vp; i++)
        use[i] = 0;
    diseffect = 0;
    for (i=0; i<total_instruction; i++)
    {
        //页面失效，不在主存中
        if (pl[page[i]].pfn == INVALID)
        {
            diseffect++;
            //无空闲页面
            if (freepf_head == NULL)
            {
                while (use[pnext -> pfn] == 1)
                {
                    use[pnext -> pfn] = 0;
                    pnext = pnext -> next;
                    if (pnext == NULL)
                        pnext = head;
                }
                //换出被替换页面
                pl[pnext -> pn].pfn = INVALID;
                swap = 1;
            }
            //如果使用位为0，则换入相应的页
            if (use[pnext -> pfn] == 0)
            {
                pl[page[i]].pfn = pnext -> pfn;  //页面结构中要标记帧号
                pnext -> pn = page[i];  //页面控制结构中要标记页号
                use[pnext -> pfn] = 1;  //重置使用位为1
                pnext = pnext -> next;  //时钟指针下移
                if (pnext == NULL)
                    pnext = head;  //如果时钟指针到达队列尾部，重新返回头部
                if (swap == 0)
                    freepf_head = freepf_head -> next;
            }
        }
    }
    printf ("%6.3f\t", 1-(float)diseffect/320);
    return 0;
}